package cn.kevenpotter.leetcode.easy.e496;

import java.util.*;

public class NextGreaterElement {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2})));
    }

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;
        Deque<Integer> stack = new LinkedList<Integer>();
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums2Length; i++) {
            while (!stack.isEmpty() && stack.peek() < nums2[i]) m.put(stack.remove(), nums2[i]);
            stack.push(nums2[i]);
        }
        int[] results = new int[nums1Length];
        for (int i = 0; i < nums1Length; i++) results[i] = m.getOrDefault(nums1[i], -1);
        return results;
    }
}
